package sort;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;

/**
 * 冒泡排序优化 如果排序过程中已经有序则中止掉
 * 但很多情况又不会有序，而且还会多执行几行代码增加了时候
 *  测试了8w数据的情况下，优化了的有没有优化的冒泡排序并没有明显的差别 好吧有一秒
 *  12s 与 11s
 */
public class BubbleSorting {
    public static void main(String[] args) {
        int[] arrays = {3, 9, -1, 10, 20};
        int[] arrays2 = {3, 4, 9, 10, 20};
        bubbleOrigin(arrays);
        //costTime();
        System.out.println("排序结束" + Arrays.toString(arrays));
    }

    /**
     *如果在某趟排序中发现没有交换，那么该数组已经有序了可以提前终止掉。
     * @param arrays
     */
    public static void bubble(int[] arrays) {
        int length = arrays.length;
        for (int i = length - 1; i > 1; i--) {
            boolean flag = true; // 结束一趟相邻排序后，flag重置为true
            for (int j = 1; j <= i; j++) {
                if (arrays[j - 1] > arrays[j]) {
                    int tmp = arrays[j];
                    arrays[j] = arrays[j - 1];
                    arrays[j - 1] = tmp;
                    flag = false;  // 标志进行过了交换，无序
                }
            }
            if (flag) {
                return;
            }
        }
    }
    public static void bubbleOrigin(int[] arrays) {
        int length = arrays.length;
        for (int i = length - 1; i >=1; i--) {
            for (int j = 1; j <= i; j++) {
                if (arrays[j - 1] > arrays[j]) {
                    int tmp = arrays[j];
                    arrays[j] = arrays[j - 1];
                    arrays[j - 1] = tmp;
                }
            }
            System.out.println(Arrays.toString(arrays));
        }
    }

    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays4 = new int[80000];
        Random random = new Random();
        for (int i = 0; i < arrays4.length; i++) {
            arrays4[i] = random.nextInt(80000);
        }
        int[] arrays3 = new int[80000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(80000);
        }

        long originStartTime = System.currentTimeMillis();
        bubbleOrigin(arrays4);
        long originEndTime = System.currentTimeMillis();
        System.out.println("程序运行时间没有优化时间为：" + (originEndTime - originStartTime)*0.001 + "s"); //输出程序运行时间
        long startTime = System.currentTimeMillis();
        bubble(arrays3);
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }
}
